'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-09 16:36:40
'''
#
# @lc app=leetcode.cn id=1090 lang=python3
#
# [1090] 受标签影响的最大值
#

# @lc code=start
# 居然是一个贪心算法，要么media呢，还以为动态规划呢。
from typing import List
class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
        import collections
        label_store = collections.defaultdict(lambda:0)
        tmp = []
        for i, v in enumerate(values):
            tmp.append((v, i))
        tmp.sort(reverse=True)
        ans = 0
        cnt = 0
        for v, i in tmp:
            if label_store[labels[i]]<use_limit:
                ans+=v
                label_store[labels[i]]+=1
                cnt+=1
            if cnt>=num_wanted:
                break
        return ans

# @lc code=end

